/*
 * Copyright (C), 2015-2018
 * FileName: Solution014
 * Author:   zhao
 * Date:     2018/7/23 22:52
 * Description: 第十四题
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

import java.util.HashMap;
import java.util.Map;

/**
 * 〈一句话功能简述〉<br>
 * 〈第十四题〉
 *
 * @author zhao
 * @date 2018/7/23 22:52
 * @since 1.0.0
 */
public class Solution014 {
  /*********************
   * 题目
   *
   * 编写一个函数来查找字符串数组中的最长公共前缀。
   *
   * 如果不存在公共前缀，返回空字符串 ""。
   *
   * 示例 1:
   *
   * 输入: ["flower","flow","flight"]
   * 输出: "fl"
   * 示例 2:
   *
   * 输入: ["dog","racecar","car"]
   * 输出: ""
   * 解释: 输入不存在公共前缀。
   * 说明:
   *
   * 所有输入只包含小写字母 a-z 。
   */

  /**************************************
   * 我的做法
   * 超过23.12%的测试案例
   *
   * ***********************************/
  public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
      return "";
    }
    int someIndex = 0;
    boolean isNeedStop = false;
    while (!isNeedStop) {
      someIndex++;
      String common = "";

      for (int i = 0; i < strs.length; i++) {
        if (someIndex > strs[i].length()) {
          isNeedStop = true;
          break;
        }

        if (i == 0) {
          common = strs[i].substring(0, someIndex);
          continue;
        }
        if (strs[i].indexOf(common) != 0) {
          isNeedStop = true;
        }

      }

    }
    return strs[0].substring(0, someIndex - 1);
  }

  /**************************************
   * 比我好的答案
   * ***********************************/
  public String better(String[] strs) {
    if (strs.length == 0) {
      return "";
    }
    String s = strs[0];
    // 找出下二项和前一项交叉的数据
    // 继续循环
    for (int i = 1; i < strs.length; i++) {
      while (strs[i].indexOf(s) != 0) {
        s = s.substring(0, s.length() - 1);
        if (s.isEmpty()) {
          return "";
        }
      }
    }
    return s;
  }

  public String better2(String[] strs) {
    if (strs.length == 0) {
      return "";
    }
    String str = strs[0];
    for (int i = 1; i < strs.length; i++) {
      while (strs[i].indexOf(str) != 0) {
        str = str.substring(0, strs.length - 1);
        if (str.isEmpty()) {
          return "";
        }
      }
    }

    return str;
  }

}